package 剑指offer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-29
 */
public class 设计LFU缓存结构 {
    public static void main(String[] args) {
        设计LFU缓存结构 lfu = new 设计LFU缓存结构();
        int[] lfu1 = lfu.LFU(new int[][]{{1, 1, 1}, {1, 1, 2}, {1, 3, 2}, {1, 2, 4}, {1, 2, 5}, {2, 2}, {1, 4, 4}, {2, 1}}, 3);
        for (int i : lfu1) {
            System.out.println(i);
        }
    }

    /**
     * lfu design
     *
     * @param operators int整型二维数组 ops
     * @param k         int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU(int[][] operators, int k) {
        // write code here

       /* 若opt=1，接下来两个整数x, y，表示set(x, y)
        若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1*/
        LFUCache cache = new LFUCache(k);
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < operators.length; i++) {
            int[] operator = operators[i];
            switch (operator[0]) {
                case 1:
                    cache.setValue(operator[1], operator[2]);
                    break;
                case 2:
                    result.add(cache.getValue(operator[1]));
                    break;
            }
        }
        int[] arr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }

    class LFUCache {

        int capacity;

        HashMap<Integer, Entry<Integer, Integer, Integer>> map;
        Entry<Integer, Integer, Integer> head;
        Entry<Integer, Integer, Integer> tail;

        public LFUCache(int capacity) {
            this.capacity = capacity;
            this.map = new HashMap<>();

        }

        public void setValue(int key, int value) {
            //1.为空
            Entry<Integer, Integer, Integer> entry = new Entry<>(key, value, 1);
            if (head == tail && head == null) {
                head = tail = entry;
                map.put(key, entry);
            }
            //2.不为空
            else {
                if (map.containsKey(key)) {
                    entry = map.get(key);
                    entry.setValue(value);
                    addCount(entry);
                } else {
                    if (map.size() < capacity) {
                        moveToHead(this.tail, entry);
                    } else {
                        //去除旧的
                        Integer eldestKey = tail.getKey();
                        map.remove(eldestKey);
                        removeEldestEntry(entry);
                    }
                    map.put(key, entry);
                }

            }

        }

        public void removeEldestEntry(Entry<Integer, Integer, Integer> newEntry) {
            Entry<Integer, Integer, Integer> pre = tail.getPre();
            pre.setNext(null);
            tail = pre;
            moveToHead(pre, newEntry);
            //移除最小的一个数

        }

        public int getValue(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            Entry<Integer, Integer, Integer> newEntry = map.get(key);
            addCount(newEntry);
            return newEntry.getValue();
        }

        public void addCount(Entry<Integer, Integer, Integer> newEntry) {

            newEntry.setCount(newEntry.getCount() + 1);
            Entry<Integer, Integer, Integer> oldPre = newEntry.getPre();
            Entry<Integer, Integer, Integer> oldNext = newEntry.getNext();
            if (oldPre != null) {
                oldPre.setNext(oldNext);
            }
            if (oldNext != null) {
                oldNext.setPre(oldPre);
            }
            moveToHead(oldPre, newEntry);
        }

        public void moveToHead(Entry<Integer, Integer, Integer> end, Entry<Integer, Integer, Integer> newEntry) {
            Entry<Integer, Integer, Integer> originalPre = newEntry.getPre();
            Entry<Integer, Integer, Integer> originalNext = newEntry.getNext();
            while (end != null && end.getCount() <= newEntry.getCount()) {
                end = end.getPre();
            }
            //最大的
            if (end == null) {
                if (head != newEntry) {
                    newEntry.setNext(this.head);
                    newEntry.setPre(null);
                    this.head.setPre(newEntry);
                    this.head = newEntry;
                }
            } else {
                Entry<Integer, Integer, Integer> next = end.getNext();
                end.setNext(newEntry);
                newEntry.setPre(end);
                if (next != null) {
                    next.setPre(newEntry);
                }
                newEntry.setNext(next);
                if (next == null) {
                    // 位置不变
                    this.tail = newEntry;
                }
            }
            //往前移动一位
            if (originalNext == null && originalPre != null) {
                this.tail = originalPre;
            }

        }

        class Entry<K, V, C> {
            K key;
            V value;
            C count;
            Entry<K, V, C> pre;
            Entry<K, V, C> next;

            public Entry<K, V, C> getPre() {
                return pre;
            }

            public void setPre(Entry<K, V, C> pre) {
                this.pre = pre;
            }

            public Entry<K, V, C> getNext() {
                return next;
            }

            public void setNext(Entry<K, V, C> next) {
                this.next = next;
            }

            public Entry(K key, V value, C count) {
                this.key = key;
                this.value = value;
                this.count = count;
            }

            public V getValue() {
                return value;
            }

            public void setValue(V value) {
                this.value = value;
            }

            public C getCount() {
                return count;
            }

            public void setCount(C count) {
                this.count = count;
            }

            public K getKey() {
                return key;
            }

            public void setKey(K key) {
                this.key = key;
            }


        }
    }
}
